package main.Q601_700;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Q631_640 {
    public static void main(String[] args) {
        System.out.println("Question631：");
        System.out.println("Question632：");
        System.out.println("Question633：平方数之和");
        System.out.println(new Question633().judgeSquareSum(3));
        System.out.println("Question634：");
        System.out.println("Question635：");
        System.out.println("Question636：");
        System.out.println("Question637：二叉树的层平均值");
        System.out.println("Question638：");
        System.out.println("Question639：");
        System.out.println("Question640：");
    }
}

class Question633{
    public boolean judgeSquareSum(int c) {
        int right=(int)Math.sqrt(c)+1,left=0;
        while (left<=right){
            if (c-(right*right)==left*left) return true;
            else if (c-(right*right)>left*left){
                left++;
            }else right--;
        }
        return false;
    }
}

class Question637{
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list=new ArrayList<>();
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size= queue.size();
                double sum=0;
                for (int i=0;i<size;i++){
                    TreeNode curNode= queue.poll();
                    sum+= curNode.val;
                    if (curNode.left!=null) queue.add(curNode.left);
                    if (curNode.right!=null) queue.add(curNode.right);
                }
                list.add(sum/size);
            }
        }
        return list;
    }
}